In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
Dysk składa się z sektorów ponumerowanych kolejno od do . Dowolny niepusty ciąg sektorów o kolejnych numerach nazywamy blokiem. Długość bloku to liczba zawartych w nim sektorów. Bloki są rozłączne, jeśli nie mają wspólnego sektora.
Na dysku są zapisane pliki. Jeden plik może być zapisany w wielu sektorach, które nie muszą tworzyć jednego bloku. Aby prawidłowo odtworzyć plik trzeba odczytać te sektory we właściwej kolejności. Ten ciąg sektorów wyznacza ciąg rozłącznych bloków, z których każdy zawiera jeden lub więcej sektorów. Sektory wewnątrz każdego bloku czyta się według kolejności numerów.
Opis rozmieszczenia pliku na dysku jest ciągiem par liczb całkowitych dodatnich. Każda taka para składa się z numeru początkowego sektora bloku oraz długości tego bloku.
Ciąg par:
7 3 2 1 5 2informuje, że treść pliku należy odczytać kolejno z sektorów o numerach: 7, 8, 9, następnie: 2, a następnie: 5, 6.
Każdy sektor na dysku może być wolny albo jest w nim zapisana część tylko jednego pliku (lub jeden cały plik).
Każdy plik ma unikalny identyfikator - dodatnią liczbę całkowitą z zakresu od do , gdzie jest liczbą plików na dysku.
Dysk jest zoptymalizowany, gdy:
Na dysku można wykonywać następujące operacje:
Kopiowanie bloku o długości trwa mikrosekund.
Zamiana zawartości dwóch bloków o długości trwa mikrosekund.
Polecenie kopiowania pliku ma postać:
K początek_bloku nowy_początek_bloku długość_bloku
Polecenie zamiany ma postać:
Z początek_bloku1 początek_bloku2 długość_blokugdzie początek_bloku oznacza numer pierwszego sektora bloku.
Ułóż program, który:
W pierwszym wierszu standardowego wejścia są zapisane dwie liczby całkowite dodatnie: liczba sektorów na dysku , nie większa niż , oraz liczba plików . Dalej w kolejnych wierszach następują opisy rozmieszczenia plików na dysku. Każdy opis pliku zawiera w pierwszym wierszu dwie liczby: identyfikator pliku z zakresu od do oraz dodatnią liczbę rozłącznych bloków, w których zapisany jest ten plik. W następnych wierszach znajduje się opis rozmieszczenia pliku w postaci odpowiedniego ciągu par liczb całkowitych dodatnich, każda para w osobnym wierszu. Liczby w wierszach są oddzielone pojedynczymi odstępami. Dane w standardowym wejściu są zapisane poprawnie i Twój program nie musi tego sprawdzać.
Standardowe wyjście ma zawierać tylko jeden wyraz NIC, gdy dysk jest już zoptymalizowany, albo ciąg poleceń, każde w osobnym wierszu. Każde polecenie musi być zapisane zgodnie z podanym poniżej formatem: najpierw duża litera K albo Z, pojedynczy odstęp, potem trzy liczby całkowite dodatnie oddzielane pojedynczymi odstępami.
Dla danych wejściowych:
200 2 2 2 51 10 41 10 1 2 71 20 11 20
poprawną odpowiedzią jest:
K 21 31 10 K 11 21 10 K 71 1 20 Z 41 51 10
Autorzy zadania: Tomasz Śmigielski, Piotr Krysiuk.